#include<iostream>

using namespace std;

struct ListNode{
    int value;
    ListNode * next;
};

// create LinkedList
ListNode * createNode(int value){
    ListNode * pHead = new ListNode();
    pHead->value = value;
    pHead -> next = nullptr;
    return pHead;
}

// connect ListNode
void connectNode( ListNode * node1 , ListNode * node2){
    node1 -> next = node2;
}

ListNode * findMeettingNode(ListNode * head){
    if ( head == nullptr )
        return nullptr;
    ListNode * pSlow = head;
    ListNode * pFast = head;
    while ( pSlow -> next != nullptr && pFast -> next -> next != nullptr ){
        pFast = pFast -> next -> next;
        pSlow = pSlow -> next;
        if ( pSlow == pFast ){
            return pFast;
        }
    }
    // 环不存在
    return nullptr;
}

// find Entry node
ListNode * entryNodeOfLoop(ListNode * head){
	ListNode * meettingNode = findMeettingNode(head);

    if ( meettingNode == nullptr )
        return nullptr;
    ListNode * pNode = head;
    while ( pNode != meettingNode ){
        pNode = pNode -> next;
        meettingNode = meettingNode-> next;
    }
    return meettingNode;
}

int main(void){
    ListNode * head = createNode(2);
    ListNode * node2 = createNode(3);
    ListNode * node3 = createNode(4);
    ListNode * node4 = createNode(5);
    ListNode * node5 = createNode(6);
    ListNode * node6 = createNode(7);
    ListNode * node7 = createNode(8);
    ListNode * node8 = createNode(9);
    ListNode * node9 = createNode(10);
    ListNode * node10 = createNode(11);

    connectNode(head, node2);
    connectNode(node2, node3);
    connectNode(node3, node4);
    connectNode(node4, node5);
    connectNode(node5, node6);
    connectNode(node6, node7);
    connectNode(node7, node8);
    connectNode(node8, node9);
    connectNode(node9, node10);
    connectNode(node10, node5);

    // 测试：链表为环/不是环； 一个节点/多个节点; 头指针为nullptr

    ListNode * node = entryNodeOfLoop(head);
    if ( node == nullptr ){
	    cout << "input param is invaild" << endl;
    }else{
        cout << node->value << endl;
    }    
    return 0;
}